/*
 * 【leetcode】103题代码 存档
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

#define N 2000

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;    //层数
    //为空则返回空
    if (root == NULL) {
        return NULL;
    }
    //初始化一个二维数组存放输出
    int** ans = malloc(sizeof(int*) * N);
    //初始化一个数组存放各行的列数（）有几个结点
    *returnColumnSizes = malloc(sizeof(int) * N);
    //初始化一个存放结点的队列
    struct TreeNode* nodeQueue[N];
    int left = 0, right = 0;

    //根结点入队
    nodeQueue[right++] = root;
    //当前队列是从左向右的
    bool isOrderLeft = true;

    //当队列不为空是进行循环，队列为空时停止循环
    while (left < right) {
        //初始化一个存放结点键值的双端队列
        int levelList[N * 2];
        int front = N, rear = N;
        int size = right - left;
        for (int i = 0; i < size; ++i) {
            struct TreeNode* node = nodeQueue[left++];
            if (isOrderLeft) {
                levelList[rear++] = node->val;
            } else {
                levelList[--front] = node->val;
            }
            if (node->left) {
                nodeQueue[right++] = node->left;
            }
            if (node->right) {
                nodeQueue[right++] = node->right;
            }
        }
        int* tmp = malloc(sizeof(int) * (rear - front));
        for (int i = 0; i < rear - front; i++) {
            tmp[i] = levelList[i + front];
        }
        ans[*returnSize] = tmp;
        (*returnColumnSizes)[*returnSize] = rear - front;
        (*returnSize)++;
        isOrderLeft = !isOrderLeft;
    }
    return ans;
}

int main()
{
    return 0;
}